Digital halftoning (or spatial dithering) is the method of rendering the illusion of continuous tone pictures in an arrangement of binary picture elements. In the case of rendering a continuous tone image with a digital output device, such as an ink jet printer or a laser printer, digital halftoning involves simulating the continuous tone image with groups or cells of dots.
In general halftoning involves generating a binary, or two-tone, image from a continuous tone, or contone or grayscale, image. Grayscale images are continuous tone black (or some other single color) and white images, whereas contone images may be either full color images or monochrome images. In either case, a halftone image is generated from a contone (full color or grayscale) image using any one of a variety of halftoning techniques, including threshold arrays or dithering (e.g., clustered dots, dispersed dots and stochastic screens), adaptive processes (e.g., error diffusion), and interactive processes (e.g., least squares and direct binary search).
Many different methods for embedding information into an image have been proposed.
For example, bar coding is a well-known category of document or image marking techniques for densely encoding digital information in a small image space without regard to how visible the encoded information is to a human viewer. A bar code symbol is a pattern of parallel bars and spaces of various widths that represent data elements or characters. The bars represent strings of binary ones and the spaces represent strings of binary zeros. A conventional “one-dimensional” bar code symbol contains a series of bars and spaces that vary only in a single dimension. One-dimensional bar code symbols have relatively small information storage capacities. “Two-dimensional” bar codes have been developed to meet the increasing need for machine-readable symbols that contain more information than one-dimensional bar code symbols. The information storage capacity of two-dimensional bar code symbols is increased relative to one-dimensional bar codes by varying the bar code patterns in two dimensions. Common two-dimensional bar code standards include PDF417, Code 1, and Maxicode. One-dimensional and two-dimensional bar code symbols typically are read by optical scanning techniques (e.g., by mechanically scanned laser beams or by self-scanning charge-coupled devices (CCD's)) that convert a printed bar code symbol into electrical signals. The electrical signals are digitized and decoded to recover the data encoded in the printed bar code symbol.
Data glyph technology is another category of information embedding techniques that is particularly advantageous for use in image applications that require a high density rate of embedded data and require the embedded data to be robust with respect to decoding. Data glyph technology encodes digital information in the form of binary 1's and 0's that are then rendered in the form of distinguishable shaped marks such as very small linear marks. Generally, each small mark represents a digit of binary data, and the linear orientation of the particular mark determines whether the particular digit is a digital 1 or 0.
Other document or image marking techniques have been proposed for embedding information in an image so that the information substantially is imperceptible to a human viewer (i.e., in a manner that simultaneously minimizes image distortion caused by embedding the information) while permitting reliable decoding of the information. For example, many different digital watermarking techniques have been proposed. In general, a digital watermark is designed to produce an embedded signal that is imperceptible to a human viewer so as not to diminish the commercial quality and value of the image being watermarked, while producing an embedded signal that is resistant to tampering.
In another approach, U.S. Pat. No. 6,141,441 discloses a technique for decoding message data that has been encoded into a printed color image as a series of small image regions (referred to as “signal cells”) that carry the encoded message. Each signal cell is composed of a spatial pattern of colored subregions that collectively have an overall average color. The colors of the subregions are defined as changes (modulations) to the average color in one or more directions in a multi-dimensional color space. The decoding technique uses a set of valid signal blocks, each of which is a unique pattern of color modulated subregions. There is a valid signal block for each valid message value defined in the coding scheme. The decoding operation first locates the positions of the signal cells in the acquired image and then subtracts the local average color of each signal cell from the cell to produce a received signal block. The decoding operation determines the respective valid signal block corresponding to each of the received signal blocks by comparing each valid signal block to each received signal block. One implementation of the decoding technique decodes signal cells that have been arranged in the acquired image in a 2D array by synchronizing an imaginary grid-like structure with the most likely position of all of the signal cells. In one embodiment, a color space direction is selected for the color modulations that results in the differently colored subregions of a signal cell being substantially imperceptible to a human viewer, thus making the pattern that carries the message substantially imperceptible in an encoded image.